package 基础练习;/**
 * @author： li
 * @date： 2022-01-11 20:01
 * @version 1.0
 */

/*
可以根据公式f(n) = k * f(n / k)建立递归，采用记忆化递归减少重复计算。
 */
import java.util.Scanner;
public class 分解质因数_公式递归版 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int begin, end;
        begin = input.nextInt();
        end = input.nextInt();
        items = new String[end + 1];
        fun(begin, end);
    }

    private static void fun(int begin, int end) {
        for (int i = begin; i <= end; i++) {
            System.out.print(i + "=");
            builder = new StringBuilder();
            decomposition(i);
            System.out.println(builder.toString());
        }
    }

    //记忆化递归
    private static String[] items;
    private static StringBuilder builder;

    private static void decomposition(int n) {
        if (items[n] != null) {
            builder.append(items[n]);
        }
        //找到第一个能够分解的素数就停止循环
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                builder.append(i + "*");
                decomposition(n / i);
                return ;
            }
        }
        builder.append(n);
        return ;
    }
}
